A cryptographic system is a computer system that uses cryptography, typically to secure or authenticate data communication between a pair of computing devices connected to one another through a data communication link in the system. Each computing device has a cryptographic unit with the processing capacity to implement one or more cryptographic protocols used to secure or authenticate the data communication. The cryptographic protocols typically perform arithmetic operations on the bit strings representing parameters, messages, or data in the protocols to produce a bit string representing the output from the protocol.
In cryptographic systems, Certification Authorities (CAs) are trusted 3rd parties responsible for vouching for the authenticity of public keys. For example, if correspondent A wishes to distribute its public key QA, correspondent A may request that a CA issue a certificate for public key QA. The certificate issued by the CA comprises a data portion and a signature portion. The data portion typically contains the identity of correspondent A, IDA, as well as the public key of correspondent A, QA. The signature portion is created by signing the data portion using the CA's private key kCA. The issued certificate therefore binds the identity information IDA of correspondent A to its public key QA through the signature of the CA.
When another correspondent, say correspondent B, receives the certificate, it can verify the signature using the public key of the CA, QCA. Successful verification confirms that the data portion of the certificate has not been compromised and that therefore correspondent B has a valid and authentic copy of the public key QA of correspondent A.
This type of certificate is referred to as a conventional or “explicit” certificate since correspondent B explicitly verifies the CA's signature on the certificate to authenticate QA. Assuming the CA has verified that correspondent A does indeed possess the private key kA associated with QA then upon verification of the signature by correspondent B, correspondent B is also assured that correspondent A must possess the private key kA associated with QA.
In order for the scheme described above to operate securely, correspondent B must be sure that he possesses a valid and authentic copy of the public key QCA of the CA. One way to achieve this is to have another CA in a higher security domain issue a certificate on public key QCA. For example, upon registration with the system, correspondent B may obtain the public key of a root CA, QCAroot. The root CA may then issue a certificate for QCA, as well as for the public keys of other CAs in the system. Correspondent B may then verify the authenticity of QCA by using the public key QCAroot of the root CA to verify the signature on the certificate issued by the root CA for the public key QCA. In this way, the root CA and its public key QCAroot form a root of trust that sits on top of a hierarchy of CAs signed above and chaining to the root CA.
Since QCAroot forms a root of trust, it is important that a correspondent or entity possessing QCAroot can be sure that their copy of QCAroot is authentic and valid. This is typically achieved by the root CA issuing a self-signed explicit certificate for its public key QCAroot. The self-signed explicit certificate is generated as the output of a trusted event, typically witnessed and recorded by company officers and external auditors on a trusted system. The issued explicit self-signed certificate comprises the root public key along with additional information that is signed by the corresponding root private key kCAroot. This additional information typically includes information such as the validity period of the key and/or key use restrictions. The recipient receives the self-signed explicit certificate, parses out the root public key QCAroot, and then uses the root public key QCAroot to verify the additional information by verifying the signature.
Certain types of implicit certificates are also known in the art as an alternative way of distributing public keys. These implicit certificates require no explicit verification of the CA's signature, and therefore have the advantage that they are smaller in size and therefore offer bandwidth savings over conventional explicit certificates. A public key distributed via such an implicit certificate is implicitly authenticated by successfully using the public key in an operation that requires the use of the corresponding private key.
A well-known implicit certificate scheme is Elliptic Curve Qu-Vanstone (ECQV). This scheme is used to provide implicit authentication when the certificate is used in conjunction with an operation requiring the sender to use the corresponding private key, such as in ECDH, ECMQV, or ECDSA operations. A summary of ECQV is as follows.
A correspondent, A, wishing to establish a private/public key pair (kA, QA) and distribute public key QA via an implicit certificate, first uses its random number generator to generate a random bit string to be used as an ephemeral private key dA. The cryptographic unit then generates a corresponding ephemeral public key GA=dAG, where G is the base point on the underlying elliptic curve and a generator of the subgroup of the elliptic curve group. Correspondent A then sends GA, as well as any identity information, to the CA. The CA receives GA and the identity information and performs the following steps:                1. Verify the received ephemeral public key GA and identity information. Verification can be done a number of ways. For example, the CA may verify that GA is a proper public key that satisfies specific criteria, such as being a point on the underlying elliptic curve, and/or satisfies defined statistical criteria.        2. Generate an ephemeral key pair (d, Q), where Q=dG.        3. Compute public-key reconstruction value BA=Q+GA.        4. Construct correspondent A certificate data IA (e.g. identity and validity information).        5. Format an implicit certificate ICA containing BA and IA.        6. Compute e=Hash(ICA).        7. Compute private key contribution data s=ed+kCA (mod n), where n is the order of base point G, and kCA is the private key of the CA.        8. Send ICA and s to correspondent A.        
Upon receiving ICA and s, correspondent A performs the following steps to calculate its key pair (kA, QA):                1. Parse out BA and IA from ICA.        2. Verify the content of IA according to the application rules. For example, this may include verifying the information is properly formatted, and/or verifying the content of IA matches the information sent by correspondent A to the CA.        3. Verify BA is a valid point on the underlying curve.        4. Compute e=Hash(ICA) and verify e≠0.        5. Compute its private key kA=edA+s (mod n).        6. Compute its corresponding public key QA=eBA+QCA, where QCA is the public key of the CA.        
The CA distributes the implicit certificate ICA to the other correspondents. A particular correspondent, say correspondent B, receives ICA and derives the public key QA of correspondent A as follows:                1. Parse out BA and IA from ICA;        2. Verify the content of IA according to the application rules, and verify BA is a valid point on the underlying curve;        3. Compute e=Hash(ICA) and verify e≠0; and        4. Compute public key QA=eBA+QCA, where QCA is the public key of the CA.        
Correspondent B is therefore able to use the public key QCA of the CA to derive QA from the implicit certificate ICA. However, correspondent B has no way of knowing whether correspondent A possesses the corresponding private key kA. Therefore, authentication of correspondent A and its public key QA is not complete until an operation involving both QA and kA is successfully performed. For example, correspondent A and correspondent B may subsequently engage in an ECMQV key agreement or ECDSA signature protocol, both of which require the use of QA and kA. If the key agreement or signature operations fail, then QA is not considered to be authentic or valid. On the other hand, if the key agreement or signature operations are successful, then correspondent A must possess kA, and the authenticity and validity of QA is implicitly verified.
Even though the CAs in such a system issue implicit certificates as above, the root CA must still distribute its root public key QCAroot in a manner that binds the identity and validity information of QCAroot to the root CA. Therefore, as described earlier, this is done by the root CA issuing a self-signed explicit certificate that is generated as the output of a trusted event. However, as mentioned earlier, an explicit certificate does not possess the bandwidth savings of an implicit certificate. Moreover, the transformations necessary to generate and operate on the self-signed explicit certificate do not complement the transformations necessary to generate and operate on the implicit certificates.